|
In the mathematical area of graph theory, a chordal bipartite graph is a bipartite graph ''B'' = (''X'',''Y'',''E'') in which every cycle of length at least 6 in ''B'' has a ''chord'', i.e., an edge that connects two vertices that are a distance > 1 apart from each other in the cycle. 〔, p. 261, , Definition 3.4.1, p. 43.〕 A better name would be weakly chordal and bipartite since chordal bipartite graphs are in general not chordal as the induced cycle of length 4 shows. ==Characterizations== Chordal bipartite graphs have various characterizations in terms of perfect elimination orderings, hypergraphs and matrices. They are closely related to strongly chordal graphs. By definition, chordal bipartite graphs have a forbidden subgraph characterization as the graphs that do not contain any induced cycle of length 3 or of length at least 5 (so-called holes) as an induced subgraph. Thus, a graph ''G'' is chordal bipartite if and only if ''G'' is triangle-free and hole-free. In , two other characterizations are mentioned: ''B'' is chordal bipartite if and only if every minimal edge separator induces a complete bipartite subgraph in ''B'' if and only if every induced subgraph is perfect elimination bipartite. Martin Farber has shown: A graph is strongly chordal if and only if the bipartite incidence graph of its clique hypergraph is chordal bipartite. 〔; , Theorem 3.4.1, p. 43.〕 A similar characterization holds for the closed neighborhood hypergraph: A graph is strongly chordal if and only if the bipartite incidence graph of its closed neighborhood hypergraph is chordal bipartite. Another result found by Elias Dahlhaus is: A bipartite graph ''B'' = (''X'',''Y'',''E'') is chordal bipartite if and only if the split graph resulting from making ''X'' a clique is strongly chordal.〔, Corollary 8.3.2, p. 129.〕 A bipartite graph ''B'' = (''X'',''Y'',''E'') is chordal bipartite if and only if every induced subgraph of ''B'' has a maximum ''X''-neighborhood ordering and a maximum Y-neighborhood ordering. Various results describe the relationship between chordal bipartite graphs and totally balanced neighborhood hypergraphs of bipartite graphs. 〔, Theorems 8.2.5, 8.2.6, pp. 126–127.〕 A characterization of chordal bipartite graphs in terms of intersection graphs related to hypergraphs is given in. A bipartite graph is chordal bipartite if and only if its adjacency matrix is totally balanced if and only if the adjacency matrix is Gamma-free. This characterization also leads to the fastest known recognition algorithm for chordal bipartite graphs: 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Chordal bipartite graph」の詳細全文を読む スポンサード リンク
|